package chapter24;

import java.util.ArrayList;
import java.util.List;
import java.util.Objects;

/**
 * 单源最短路径-Dijkstra
 */
public class SingleSource_Dijkstra {

    public static void Dijkstra(Graph G, EdgeNode s) {
        initializeSingleSource(G, s);
        List<EdgeNode> edges = new ArrayList<>();
        for (VertexNode v : G.adjList) {
            EdgeNode pre = v.firstEdge;
//            while (pre != null) {
//                if (pre.key != pre.firstEdge.key) {
                    edges.add(pre);
//                }
//                pre = pre.next;
//            }
        }
        sort(edges);
        for (EdgeNode u : edges) {
            EdgeNode v = u.next;
            while (v != null) {
                EdgeNode v1 = G.adjList.get(v.adj).firstEdge;
                relax(u, v1, v.weight);

                v = v.next;
            }
        }
    }

    private static void sort(List<EdgeNode> edges) {
        sort(edges, 0, edges.size() - 1);
    }

    private static void sort(List<EdgeNode> edges, int p, int r) {
        if (p < r) {
            int q = partition(edges, p, r);
            sort(edges, p, q - 1);
            sort(edges, q + 1, r);
        }
    }

    private static int partition(List<EdgeNode> edges, int p, int r) {
        EdgeNode edge = edges.get(r);
        int i = p - 1;
        for (int j = p; j <= r - 1; j++) {
            if (edges.get(j).key < edge.key) {
                i++;
                EdgeNode temp = edges.get(j);
                edges.set(j, edges.get(i));
                edges.set(i, temp);
            }
        }
        EdgeNode temp = edges.get(i + 1);
        edges.set(i + 1, edges.get(r));
        edges.set(r, temp);
        return i + 1;
    }

    private static void initializeSingleSource(Graph G, EdgeNode s) {
        for (VertexNode v : G.adjList) {
            v.firstEdge.d = Integer.MAX_VALUE;
            v.firstEdge.pai = null;
        }
        s.firstEdge.d = 0;
    }


    private static void relax(EdgeNode u, EdgeNode v, int w) {
        if (v.d > u.d + w) {
            v.d = u.d + w;
            v.pai = u;
        }
    }

    public static void insert(EdgeNode x, EdgeNode y, int w) {
        EdgeNode pre = x;
        while (pre.next != null) {
            pre = pre.next;
        }
        y.firstEdge = x;
        y.weight = w;
        pre.next = y;
    }

    public static class EdgeNode {
        public char key;
        public int weight;
        public EdgeNode firstEdge = this;
        public EdgeNode next;
        public int adj;
        public int d = Integer.MAX_VALUE;
        public EdgeNode pai;

        public EdgeNode(char key, int adj) {
            this.key = key;
            this.adj = adj;
        }

        public int getWeight() {
            return weight;
        }

        @Override
        public boolean equals(Object o) {
            if (this == o) return true;
            if (o == null || getClass() != o.getClass()) return false;
            EdgeNode edgeNode = (EdgeNode) o;
            return Objects.equals(key, edgeNode.key);
        }

        @Override
        public int hashCode() {
            return Objects.hash(key);
        }

        @Override
        public String toString() {
            return "{" +
                    "u='" + firstEdge.key + '\'' +
                    ", v='" + key + '\'' +
                    ", d=" + d +
                    '}';
        }
    }

    public static class VertexNode {
        public String key;
        public EdgeNode firstEdge;

        public VertexNode(EdgeNode firstEdge) {
            this.firstEdge = firstEdge;
        }

        @Override
        public String toString() {
            return "VertexNode{" +
                    "key='" + key + '\'' +
                    ", firstEdge=" + firstEdge +
                    '}';
        }
    }

    public static class Graph {
        public List<VertexNode> adjList = new ArrayList<>();
        public int numVertexes;
        public int numEdges;

        @Override
        public String toString() {
            return "Graph{" +
                    "adjList=" + adjList +
                    ", numVertexes=" + numVertexes +
                    ", numEdges=" + numEdges +
                    '}';
        }
    }
}
